package com.fzk.core.lru;

import com.fzk.core.lru.NodeList.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;

/**
 * LRU实现
 * 维护了2个链表，插入时插入链表2的头部，相当于插入整个lru的中间，
 * 从而将老化时间缩短到一半，避免偶然访问的冷数据在lru中停留过长时间。
 * 已在链表中的数据再次访问时将其移到链表1的头部。
 *
 * @author fzk
 * @datetime 2023-05-11 22:28:10
 */
public abstract class LruList<K, V> {
    public final int capacity;
    private final NodeList<K, V> list1;
    private final NodeList<K, V> list2;

    public LruList(int capacity) {
        if (capacity < 4 || capacity > 1024 * 1024 || (capacity & 1) != 0) {
            throw new RuntimeException(String.format("capacity: %d, 必须为偶数, 且>=4, 且<=1024*1024", capacity));
        }
        this.capacity = capacity;
        list1 = new NodeList<>();
        list2 = new NodeList<>();
    }

    public synchronized V get(K key) {
        V val;
        if ((val = list1.get(key)) != null) {
            list1.moveToHead(key);
        } else if ((val = list2.get(key)) != null) {
            // 从list2移除并放入list1头部
            list2.remove(key);
            if (isFull(list1)) {
                // 如果list1已经满了，就移除list1末尾并放入list2头部
                Node<K, V> l1LastNode = list1.removeLast();
                list2.putHead(l1LastNode.key, l1LastNode.val);// 此时list2必然未满
            }
            // 放入list1头部
            list1.putHead(key, val);
        }
        maintain();// 维护链表长度
        return val;
    }

    public synchronized V put(K key, V val) {
        V old = null;
        if (list1.containsKey(key)) {
            old = list1.replace(key, val);
            moveToHead(key);// 移到lru队头
        } else if (list2.containsKey(key)) {
            old = list2.replace(key, val);
            moveToHead(key);// 移到lru队头
        } else {
            // list2满了则必然则整个链表都满了
            if (isFull(list2)) {
                removeLast();
            }
            // 插入整个lru链表的中间，即list2的头部
            list2.putHead(key, val);
        }
        maintain();// 维护链表长度
        if (old != null) {// 释放资源回调
            removeCallback(key, old);
        }
        // 插入回调
        putCallback(key, val);
        return old;
    }

    public synchronized V remove(K key) {
        V old = null;
        if (list1.containsKey(key)) {
            old = list1.remove(key);
        } else if (list2.containsKey(key)) {
            old = list2.remove(key);
        }

        maintain();// 维护链表长度
        if (old != null) {// 释放资源回调
            removeCallback(key, old);
        }
        return old;
    }

    private void moveToHead(K key) {
        if (list1.containsKey(key)) {
            list1.moveToHead(key);
        } else if (list2.containsKey(key)) {
            // 从list2移除，放入list1头部
            V remove = list2.remove(key);
            if (isFull(list1)) {// list1满了则将其末尾的放入list2头部
                Node<K, V> l1Last = list1.removeLast();
                list2.putHead(l1Last.key, l1Last.val);
            }
            list1.putHead(key, remove);// 放入list1头部
        }
    }

    private Node<K, V> removeLast() {
        Node<K, V> last = null;
        if (list2.size() > 0) {
            last = list2.removeLast();
        } else if (list1.size() > 0) {
            last = list1.removeLast();
        }
        maintain();// 维护lru两个队列
        if (last != null)// 释放资源回调
            removeCallback(last.key, last.val);
        return last;
    }

    /**
     * 插入lru缓存队列成功时的回调
     */
    protected abstract void putCallback(K key, V val);

    /**
     * 当移除队尾时，回调此方法
     * 可在此释放资源
     */
    protected abstract void removeCallback(K key, V val);

    public synchronized boolean containsKey(K key) {
        return list1.containsKey(key) || list2.containsKey(key);
    }

    // 维护list1等于list2或 list1.size()=list2.size()+1
    private void maintain() {
        if (list1.size() == list2.size()) {
            return;
        }
        // 维护两个链表尽可能的长度相等
        // l1比l2长超过1个，则将l1的尾部结点移到l2的头部
        while (list1.size() - 1 > list2.size()) {
            Node<K, V> l1Last = list1.removeLast();
            list2.putHead(l1Last.key, l1Last.val);
        }
        // l2比l1长，则将l2头部结点移到l1的尾部
        while (list2.size() > list1.size()) {
            Node<K, V> l2Head = list2.removeHead();
            list1.putTail(l2Head.key, l2Head.val);
        }
    }

    public synchronized int size() {
        return list1.size() + list2.size();
    }

    // 瞬间快照
    public synchronized Map<K, V> kvMap() {
        HashMap<K, V> map = new HashMap<>(list1.size() + list2.size());
        list1.toArray().forEach((kvNode -> map.put(kvNode.key, kvNode.val)));
        list2.toArray().forEach((kvNode -> map.put(kvNode.key, kvNode.val)));
        return map;
    }

    public synchronized String toString() {
        return String.format("list1: %s, list2: %s", list1.toString(), list2.toString());
    }

    private boolean isFull(NodeList<K, V> list) {
        return list.size() >= capacity / 2;
    }

    // 清空缓存队列
    public synchronized void clear() {
        ArrayList<Node<K, V>> arr = new ArrayList<>(size());
        arr.addAll(list1.toArray());
        arr.addAll(list2.toArray());
        list1.clear();
        list2.clear();
        // 移除回调
        for (Node<K, V> node : arr) {
            removeCallback(node.key, node.val);
        }
    }

    public void check() {
        if (list1.size() == list2.size() || list1.size() == list2.size() + 1) {
            list1.checkList();
            list2.checkList();
        } else {
            throw new RuntimeException(String.format("非法, list1.size: %d, list2.size: %d", list1.size(), list2.size()));
        }
    }

    public static void main(String[] args) {
        // 测试
        LruList<String, Integer> lru = new LruList<>(8) {
            @Override
            protected void putCallback(String key, Integer val) {
                System.out.println("入队列: " + key);
            }

            @Override
            protected void removeCallback(String key, Integer val) {
                System.out.println("出队列: " + key);
            }
        };
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            String key = String.format("%03d", i);
            arr.add(key);
            lru.put(key, i);
            lru.check();

            Integer get = lru.get(String.format("%03d", ThreadLocalRandom.current().nextInt(0, arr.size())));
            if (get != null) {
                System.out.println("get: " + get);
                lru.check();
            }
            Integer remove = lru.remove(String.format("%03d", ThreadLocalRandom.current().nextInt(0, arr.size())));
            if (remove != null) {
                System.out.println("remove: " + remove);
                lru.check();
            }
            System.out.println(lru);
        }
    }
}
